Consider the problem of building a communication switch with N input ports and N output ports. If we place the buffers at the output ports, then we need to use memory with bandwidth equal to the sum of the bandwidths of the input ports. This can be done by using fast static memory with very wide memory buses. Using the current memory technology, this solution is only cost effective when the aggregate bandwidth of the switch is less than 50 Gbits/sec. Therefore, virtual output queued (VOQ) architecture is an attractive option for building switches with higher aggregate bandwidth. However, since the hardware complexity of the arbiter is O(N2), the VOQ switches are only practical for switches with a moderate number of switch ports (e.g. N≦32). Note that the number of switch ports is equal to the number of line cards. The actual number of switch ports can be larger as multiple ports can be multiplexed/demultiplexed by the line cards. In a switch with the VOQ architecture, the memory write bandwidth is equal to the input port bandwidth and the read bandwidth is equal to the switch bandwidth. The bandwidth of a cross-connect (FIG. 1A) is higher than the maximum port bandwidth by a speedup factor. The arbiter has to operate at or above the maximum port bandwidth. The output buffers need to have a read bandwidth equal to the output port bandwidth and write bandwidth equal to the bandwidth of the switching fabric.
Extensive work on the problem of enhancing the throughput of input buffered switches has been described by N. W. McKeown in an article entitled “The iSLIP scheduling algorithm for input-queued switches,” IEEE/ACM Transactions on Networking, vol. 7, no. 2, April 1999 and by N. W. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, and M. Horowitz in another article entitled “The tiny tera: A packet switch core,” in Hot Interconnects V, August 1996. Both these articles are incorporated by reference herein in their entirety. The arbitration problem is equivalent to a bipartite matching problem for which the best known algorithm has a time complexity of the order of nn/2 as described by J. E. Hopcroft and R. M. Karp, in an article entitled “An n5/2 algorithm for maximum matchings for bipartitle graphs,” SIAM Journal on Computing, vol. 2, no. 4, pp. 225-231, 1973. This article is also incorporated by reference herein in its entirety.
A hardware arbiter has to make arbitration decisions within one cell interval of the switching fabric. This can only be achieved by using parallelism and careful methods to minimize probability of “synchronization” of decisions by independent modules working in parallel. One way of building an arbiter is by using two sets of N independent schedulers as shown in FIG. 1B. The jth scheduler in the first set corresponds to the jth output port and the ith scheduler in the second set corresponds to the ith input port. The jth output port scheduler selects an input port from the set of input ports that have indicated cell arrival to the jth output port. And the ith input port scheduler selects an output port from the set of output ports which had selected the ith input port in the first step. Any unmatched input and output ports are matched in the subsequent iteration(s). A prior art method called Parallel Iterative Matching (PIM) arbitration algorithm uses random schedulers: A requesting port is selected with uniform probability. This algorithm is further described by T. Anderson, S. Owicki, J. Saxe, and C. Thacker in an article entitled “High speed switch scheduling for local area networks,” ACM Transactions on Computer Systems, vol. 11, no. 4, pp. 319-352, November 1993 that is incorporated by reference herein in its entirety.
Another method, namely the iSLIP arbitration algorithm described in the article entitled “The iSLIP scheduling algorithm for input-queued switches,” uses round-robin schedulers. In the case of iSLIP, the schedulers are not truly independent: The round-robin scheduler in the input unit is only advanced if its selection is accepted by the round-robin scheduler at the output unit. Various weighted versions of the round-robin schedulers are used in commercial switches. However, it must be noted that a simple weighted round-robin scheme is not suitable as it increases the probability of “synchronization.” “Synchronization” occurs when more than one scheduler selects the same port repeatedly thus reducing the switch throughput. McKeown suggested the use of circular schedule lists to implement weighted iSLIP arbiters. However, very large schedule lists are needed and programming these lists as connections are added and deleted is not a trivial problem. Moreover, the two sets of schedulers use two sets of weights and there does not seem to be a simple relationship between the weights and the bandwidth allocated to the flows. The main drawback, however, of the arbiters using two sets of schedulers is that these arbiters do not provide fairness of the type described by D. Cavendish, M. Goudreau, and A. Ishii, in an article entitled “On the fairness of scheduling algorithms for input-queued switches,” in International Teletraffic Congress, December 2001, vol. 4, pp. 829-841 which is incorporated by reference herein in its entirety.